package com.hqq.exercise.divide_conquer;

/**
 * MonoSum 数组单调和
 * 题目描述:
 * 现定义数组单调和为所有元素i的f(i)值之和。这里的f(i)函数定义为元素i左边(不包括其自-xx身)小于等于它的数字之和。请设计一个高效算法，计算数组的单调和。
 * 给定一个数组A同时给定数组的大小n，请返回数组的单调和。，同时保证单调和不会保证数组大小小于等于500超过int范围。
 * 样例输入:
 * [1,3,5,2,4,6],6
 * 样例输出:
 * 27
 * 思路:
 * 1.最简单的方法 计算每个元素的f(i) 统计他们的总和
 * 2.这题利用归并排序的特点：在归并阶段，比如左边{2, 5} 右边{3, 6}。
 * 左边的2肯定在3和6的前面，5也肯定在6前面，所以此次归并可以算一个单调和2 * 2 + 5 * 1=9。每次归并都计算就可得到总的和
 * Created by heqianqian on 2017/8/26.
 */
public class MonoSum {

    private static int count = 0;

    public static void main(String[] args) {
        int[] array = new int[]{1, 3, 5, 2, 4, 6};
        int result = calcMonoSum(array, array.length);
        System.out.println(result);
        mergeSort(array);
        System.out.println(count);
    }

    public static int calcMonoSum(int[] A, int n) {
        if (A == null || A.length == 0 || n < 0 || n > A.length) {
            throw new IllegalArgumentException("Wrong Input");
        }
        int sum = 0;
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (A[j] <= A[i]) {
                    sum += A[j];
                }
            }
        }
        return sum;
    }

    //测试手写归并排序
    public static int[] mergeSort(int[] array) {
        //异常输入判断
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("Array is null");
        }
        int[] result = new int[array.length];
        mergeSort(array, 0, array.length - 1, result);
        return result;
    }

    private static void mergeSort(int[] array, int start, int end, int[] result) {
        if (start < end) {
            int mid = (start + end) / 2;
            mergeSort(array, start, mid, result);
            mergeSort(array, mid + 1, end, result);
            mergeArray(array, start, mid, end, result);
        }
    }

    private static void mergeArray(int[] array, int start, int mid, int end, int[] result) {
        int aIndex = start, bIndex = mid + 1;//两个数组的下标索引
        int rIndex = 0;//目的数组的下标索引
        while (aIndex <= mid && bIndex <= end) {
            /*只要两个数组都还存在元素 就取出两个数组中较小的那个元素*/
            /*前提是两个数组都是有序数组*/
            if (array[aIndex] <= array[bIndex]) {
                count += array[end - bIndex + 1] * array[aIndex];
                System.out.println(array[aIndex] + " " + array[bIndex]);
                result[rIndex++] = array[aIndex++];
            } else {
                result[rIndex++] = array[bIndex++];
            }
        }
        while (aIndex <= mid) {
            result[rIndex++] = array[aIndex++];
        }
        while (bIndex <= end) {
            result[rIndex++] = array[bIndex++];
        }
        for (int i = 0; i < rIndex; i++) {
            array[start + i] = result[i];
        }
    }


}
